/**
 * 
 */
package com.dalonedrau.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.Vector;

/**
 * @author Donald
 */
public final class RiverGraphSearch {
	private static final int	NO_PARENT_ASSIGNED	= -3;
	private static final int	UNVISITED			= -2;
	private static final int	VISITED				= -1;
	/** flag indicating that the target has been found. */
	private boolean				found;
	/** the graph being searched. */
	private SparseGraph<RiverNode, GraphEdge>		graph;
	/** the route to the target. */
	private int[]				route;
	/** the source node from where the search originates. */
	private int					source;
	/** the target node from where the search ends. */
	private int					target;
	/** the vector of all nodes visited as part of the search. */
	private int[]				visited;
	/**
	 * Creates a new instance of {@link RiverGraphSearch}.
	 * @param graph
	 */
	public RiverGraphSearch(final SparseGraph<RiverNode, GraphEdge> g) {
		graph = g;
		source = -1;
		target = -1;
		found = false;
		visited = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < visited.length; i++) {
			visited[i] = RiverGraphSearch.UNVISITED;
		}
		route = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < route.length; i++) {
			route[i] = RiverGraphSearch.NO_PARENT_ASSIGNED;
		}
		//this.shortestPathTree = new Vector<GraphEdge>();
	}
	public void clear() {
		source = -1;
		target = -1;
		found = false;
		for (int i = 0; i < visited.length; i++) {
			visited[i] = RiverGraphSearch.UNVISITED;
		}
		for (int i = 0; i < route.length; i++) {
			route[i] = RiverGraphSearch.NO_PARENT_ASSIGNED;
		}
	}
	/**
	 * Gets the graph
	 * @return {@link SparseGraph}
	 */
	public SparseGraph getGraph() {
		return graph;
	}
	public Integer[] getPathToTarget() {
		ArrayList<Integer> path = new ArrayList<Integer>();
		// just return an empty path if no path to target found or if
		// no target has been specified
		// if there is no path to the target, or no target was specified,
		// an empty path is returned. otherwise, the path is filled below
		if (found && target >= SparseGraph.INVALID_NODE_INDEX) {
			int node = target;
			path.add(node);
			while (node != source) {
				node = route[node];
				path.add(0, node);
			}
		}
		return path.toArray(new Integer[path.size()]);
	}
	/**
	 * Determines if the target node has been found.
	 * @return true if the target node has been found; false otherwise
	 */
	public boolean isFound() {
		return found;
	}
	public void search(final int src, final int targ) throws Exception {
		source = src;
		target = targ;
		for (int i = 0; i < visited.length; i++) {
			visited[i] = RiverGraphSearch.UNVISITED;
		}
		for (int i = 0; i < route.length; i++) {
			route[i] = RiverGraphSearch.NO_PARENT_ASSIGNED;
		}
		found = searchBreadthFirst();
	}
	public void searchRiverOnlyPath(final int src, final int targ) throws Exception {
		source = src;
		target = targ;
		for (int i = 0; i < visited.length; i++) {
			visited[i] = RiverGraphSearch.UNVISITED;
		}
		for (int i = 0; i < route.length; i++) {
			route[i] = RiverGraphSearch.NO_PARENT_ASSIGNED;
		}
		found = this.searchBreadthRiver();
	}
	private GraphEdge[] shortestPathTree;
	private double[] costToThisNode;
	private GraphEdge[] searchFrontier;
	/*
	private void searchDijkstra() throws Exception {
		 //create an indexed priority queue that sorts smallest to largest
		  //(front to back). Note that the maximum number of elements the iPQ
		  //may contain is NumNodes(). This is because no node can be represented
		  // on the queue more than once.
		  PriorityQueue<Double> pq = new PriorityQueue<Double>(graph.getNumberOfNodes());

		  //put the source node on the queue
		  pq.offer(new Double(source));

		  //while the queue is not empty
		  while(!pq.isEmpty()) {
		    //get the lowest cost node from the queue. Don't forget, the return value
		    //is a *node index*, not the node itself. This node is the node not already
		    //on the SPT that is the closest to the source node
		    int nextClosestNode = pq.poll().intValue();

		    //move this edge from the search frontier to the shortest path tree
		    shortestPathTree[nextClosestNode] = searchFrontier[nextClosestNode];

		    //if the target has been found exit
		    if (nextClosestNode == target) return;

		    //now to relax the edges. For each edge connected to the next closest node
			// push the edges leading from the node at the end of this edge
			// onto the queue
			GraphEdge[] edges = graph.getEdgesFromNode(nextClosestNode);
			for (int i = 0; i < edges.length; i++) {
		        //the total cost to the node this edge points to is the cost to the
		        //current node plus the cost of the edge connecting them.
				double cost = 1;
				if (edges[i] instanceof WeightedGraphEdge) {
					cost = ((WeightedGraphEdge) edges[i]).getCost();
				}
		        double newCost = costToThisNode[nextClosestNode] + cost;

		        //if this edge has never been on the frontier make a note of the cost
		        //to reach the node it points to, then add the edge to the frontier
		        //and the destination node to the PQ.
		        if (searchFrontier[edges[i].getTo()] == 0)
		        {
		          m_CostToThisNode[pE->To()] = NewCost;

		          pq.insert(pE->To());

		          m_SearchFrontier[pE->To()] = pE;
		        }

		        //else test to see if the cost to reach the destination node via the
		        //current node is cheaper than the cheapest cost found so far. If
		        //this path is cheaper we assign the new cost to the destination
		        //node, update its entry in the PQ to reflect the change, and add the
		        //edge to the frontier
		        else if ( (NewCost < m_CostToThisNode[pE->To()]) &&
		                  (m_ShortestPathTree[pE->To()] == 0) )
		        {
		          m_CostToThisNode[pE->To()] = NewCost;
		        //because the cost is less than it was previously, the PQ must be
		        //resorted to account for this.
		        pq.ChangePriority(pE->To());

		        m_SearchFrontier[pE->To()] = pE;
		      }
		    }
		  }
	}
	*/
	private boolean searchBreadthFirst() throws Exception {
		// create a queue of edges
		LinkedList<GraphEdge> list = new LinkedList<GraphEdge>();
		// create an initial dummy edge and push it on the queue
		GraphEdge dummy = new GraphEdge(source, source);
		list.offer(dummy);
		// mark the source node as visited
		visited[source] = RiverGraphSearch.VISITED;
		// while there are edges in the queue keep searching
		while (!list.isEmpty()) {
			// grab the next edge
			GraphEdge next = list.poll();
			// make a note of the parent of the node this edge points to
			route[next.getTo()] = next.getFrom();
			// test for termination. If the edge's destination node is
			// the target node, then the search can return success
			if (next.getTo() == target) {
				//System.out.println("found target");
				return true;
			}

			// push the edges leading from the node at the end of this edge
			// onto the queue
			GraphEdge[] edges = graph.getEdgesFromNode(next.getTo());
			for (int i = 0; i < edges.length; i++) {
				//System.out.println("found edge from "+edges[i].getFrom()+" to "+edges[i].getTo());
				// if the node hasn't already been visited we can push the
				// edge onto the queue
				if (visited[edges[i].getTo()] == RiverGraphSearch.UNVISITED) {
					list.offer(edges[i]);

					// the node is marked as visited here, BEFORE it is
					// examined, because
					// it ensures a maximum of N edges are ever placed in the
					// queue,
					// rather than E edges.
					visited[edges[i].getTo()] = RiverGraphSearch.VISITED;
				}
			}
		}
		return false;
	}
	private boolean searchBreadthRiver() throws Exception {
		// create a queue of edges
		LinkedList<GraphEdge> list = new LinkedList<GraphEdge>();
		// create an initial dummy edge and push it on the queue
		GraphEdge dummy = new GraphEdge(source, source);
		list.offer(dummy);
		// mark the source node as visited
		visited[source] = RiverGraphSearch.VISITED;
		// while there are edges in the queue keep searching
		while (!list.isEmpty()) {
			// grab the next edge
			GraphEdge next = list.poll();
			// make a note of the parent of the node this edge points to
			route[next.getTo()] = next.getFrom();
			// test for termination. If the edge's destination node is
			// the target node, then the search can return success
			if (next.getTo() == target) {
				//System.out.println("found target");
				return true;
			}

			// push the edges leading from the node at the end of this edge
			// onto the queue
			GraphEdge[] edges = graph.getEdgesFromNode(next.getTo());
			for (int i = 0; i < edges.length; i++) {
				//System.out.println("found edge from "+edges[i].getFrom()+" to "+edges[i].getTo());
				// if the node hasn't already been visited we can push the
				// edge onto the queue
				if (visited[edges[i].getTo()] == RiverGraphSearch.UNVISITED) {
					// only push river edges onto the list
					// if the edge points to a river node, 
					// or points to the target, push it on
					if (((RiverNode) graph.getNode(edges[i].getTo())).getType() 
							== RiverNode.TYPE_RIVER
							|| edges[i].getTo() == target) {
					list.offer(edges[i]);

					// the node is marked as visited here, BEFORE it is
					// examined, because
					// it ensures a maximum of N edges are ever placed in the
					// queue,
					// rather than E edges.
					visited[edges[i].getTo()] = RiverGraphSearch.VISITED;
					}
				}
			}
		}
		return false;
	}
	private boolean searchDepthFirst() throws Exception {
		// create a stack of edges
		Stack<GraphEdge> stack = new Stack<GraphEdge>();
		// create an initial dummy edge and push it on the stack
		GraphEdge dummy = new GraphEdge(source, source);
		stack.push(dummy);
		// while there are edges on the stack keep searching
		while (!stack.isEmpty()) {
			// grab the next edge
			GraphEdge next = stack.pop();
			// make a note of the parent of the node this edge points to
			route[next.getTo()] = next.getFrom();
			// mark the edge's destination node as visited
			visited[next.getTo()] = RiverGraphSearch.VISITED;
			
			// test for termination. If the edge's destination node is
			// the target node, then the search can return success
			if (next.getTo() == target) {
				return true;
			}
			// push all edges from the node the current edge points to
			// onto the stack. ignore all edges that point to a node that
			// has been visited
			GraphEdge[] edges = graph.getEdgesFromNode(next.getTo());
			for (int i = 0; i < edges.length; i++) {
				if (visited[edges[i].getTo()] == RiverGraphSearch.UNVISITED) {
					stack.push(edges[i]);
				}
			}
		}
		return false;
	}

	/**
	 * Sets the graph
	 * @param graph the graph to set
	 */
	public void setGraph(SparseGraph graph) {
		this.graph = graph;
	}
}